Матч 381, Лорд чисел (TheNumbersLord)

Дивизион 2, Уровень 3

Массив numbers содержит набор положительных целых чисел. Необходимо выбрать из массива n чисел и склеивая их в произвольном порядке, составить наибольшее число. Одно и то же число из массива можно выбирать несколько раз, но каждое число должно быть выбрано как минимум один раз.

Результирующее наибольшее число вернуть в виде строки.

Класс: TheNumbersLord

Метод: string create(vector<int> numbers, int n)

Ограничения: numbers содержит от 1 до 50 чисел, 1 ≤ numbers[i] ≤ 10⁹, n изменяется от количества чисел в массиве numbers до 50.

Вход. Массив чисел numbers и число n.

Выход. Наибольшее число, которое можно получить, склеивая n выбранных чисел.

Пример входа

numbers	n
{4, 7}	4
{1, 10, 100}	4
{4,4,4,4}	9
{1,1,2}	3

Пример выхода

“7774”

“110100100”

“444444444”

“211”

РЕШЕНИЕ

жадный алгоритм + сортировка

Рассмотрим заданные числа как строки и занесем их в массив строк s. Если значение n больше количества чисел в numbers, то очевидно, что необходимо выбрать (и занести в массив s) лексикографически наибольшее число из массива numbers еще n – numbers.size() раз.

Отсортируем строки массива s согласно правилу: строка a меньше строки b тогда и только тогда, когда строка a + b меньше строки b + a (‘+’ – операция конкатенации строк). Строки сортируются по убыванию.

Конкатенация строк отсортированного подобным образом массива s образует искомое наибольшее число.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <numeric>

#include <algorithm>

using namespace std;

vector<string> s;

char temp[100];

int f(string a, string b)

{

return a+b > b+a;

}

class TheNumbersLord

{

public:

string create(vector<int> numbers, int n)

{

int i;

sort(numbers.begin(),numbers.end());

for(i = 0; i < numbers.size(); i++)

{

sprintf(temp,"%d",numbers[i]);

s.push_back(temp);

}

for(i = s.size(); i < n; i++) s.push_back(temp);

sort(s.begin(),s.end(),f);

return accumulate(s.begin(),s.end(),string());

}

};